package graph.digraph;

import linear.Stack;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 基于深度优先的顶点排序
 */
public class DepthFirstOrder {
    private boolean[] marked;
    private Stack<Integer> reversePost;

    public DepthFirstOrder(Digraph G) {
        this.marked = new boolean[G.V()];
        reversePost = new Stack<>();

        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]) {
                dfs(G, v);
            }
        }
    }

    /**
     * 获取线性序列
     */
    public Stack<Integer> reversePost() {
        return reversePost;
    }

    /**
     * 基于深度优先 生成顶点序列
     */
    private void dfs(Digraph G, int v) {
        marked[v] = true;

        for (Integer w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w);
            }
        }
        // 当前点搜索完毕 入栈
        reversePost.push(v);

    }


    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(DirectedCycle.class.getClassLoader().getResourceAsStream("road_find.txt")));
        int number = Integer.parseInt(reader.readLine());
        Digraph G = new Digraph(number);
        int roadNumber = Integer.parseInt(reader.readLine());
        // 循环读取道路，并调用addEdge方法
        for (int i = 0; i < roadNumber; i++) {
            String line = reader.readLine();
            int p = Integer.parseInt(line.split(" ")[0]);
            int q = Integer.parseInt(line.split(" ")[1]);
            G.addEdge(p, q);
        }
        // 创建测试对象
        DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
        for (Integer v : depthFirstOrder.reversePost()) {
            System.out.print(v + " ->");
        }
    }
}
